{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Print Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: printTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #输出二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树的根节点 <code>root</code> ，请你构造一个下标从 <strong>0</strong> 开始、大小为 <code>m x n</code> 的字符串矩阵 <code>res</code> ，用以表示树的 <strong>格式化布局</strong> 。构造此格式化布局矩阵需要遵循以下规则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树的 <strong>高度</strong> 为 <code>height</code> ，矩阵的行数 <code>m</code> 应该等于 <code>height + 1</code> 。</li>\n",
    "\t<li>矩阵的列数 <code>n</code> 应该等于 <code>2<sup>height+1</sup> - 1</code> 。</li>\n",
    "\t<li><strong>根节点</strong> 需要放置在 <strong>顶行</strong> 的 <strong>正中间</strong> ，对应位置为 <code>res[0][(n-1)/2]</code> 。</li>\n",
    "\t<li>对于放置在矩阵中的每个节点，设对应位置为 <code>res[r][c]</code> ，将其左子节点放置在 <code>res[r+1][c-2<sup>height-r-1</sup>]</code> ，右子节点放置在 <code>res[r+1][c+2<sup>height-r-1</sup>]</code> 。</li>\n",
    "\t<li>继续这一过程，直到树中的所有节点都妥善放置。</li>\n",
    "\t<li>任意空单元格都应该包含空字符串 <code>\"\"</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回构造得到的矩阵<em> </em><code>res</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/03/print1-tree.jpg\" style=\"width: 141px; height: 181px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2]\n",
    "<strong>输出：</strong>\n",
    "[[\"\",\"1\",\"\"],\n",
    "&nbsp;[\"2\",\"\",\"\"]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/03/print2-tree.jpg\" style=\"width: 207px; height: 302px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,null,4]\n",
    "<strong>输出：</strong>\n",
    "[[\"\",\"\",\"\",\"1\",\"\",\"\",\"\"],\n",
    "&nbsp;[\"\",\"2\",\"\",\"\",\"\",\"3\",\"\"],\n",
    "&nbsp;[\"\",\"\",\"4\",\"\",\"\",\"\",\"\"]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数在范围 <code>[1, 2<sup>10</sup>]</code> 内</li>\n",
    "\t<li><code>-99 &lt;= Node.val &lt;= 99</code></li>\n",
    "\t<li>树的深度在范围 <code>[1, 10]</code> 内</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [print-binary-tree](https://leetcode.cn/problems/print-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [print-binary-tree](https://leetcode.cn/problems/print-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2]', '[1,2,3,null,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTreeDepth(self, cur: TreeNode) -> int:\n",
    "        return (\n",
    "            0 if cur is None else\n",
    "            1 + max(self.findTreeDepth(cur.left), self.findTreeDepth(cur.right))\n",
    "        )\n",
    "\n",
    "\n",
    "    def printTreeR(\n",
    "        self, cur: TreeNode, row: int, col: int, tree_depth: int, grid: List[List[str]]\n",
    "    ) -> int:\n",
    "        if row == tree_depth:\n",
    "            return col\n",
    "\n",
    "        col = self.printTreeR(\n",
    "            cur.left if cur is not None else None, row + 1, col, tree_depth, grid\n",
    "        )\n",
    "\n",
    "        grid[row].extend([\"\"] * (col - len(grid[row])))\n",
    "        grid[row].append(str(cur.val) if cur is not None else \"\")\n",
    "        \n",
    "        return self.printTreeR(\n",
    "            cur.right if cur is not None else None, row + 1, col + 1, tree_depth, grid\n",
    "        )\n",
    "\n",
    "\n",
    "    def printTree(self, root: TreeNode) -> List[List[str]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "\n",
    "        tree_depth: int = self.findTreeDepth(root)\n",
    "        grid: List[List[str]] = [[] for _ in range(tree_depth)]\n",
    "        self.printTreeR(root, 0, 0, tree_depth, grid)\n",
    "        \n",
    "        max_row_len: int = max(len(row) for row in grid)\n",
    "        for row in grid:\n",
    "            row.extend([\"\"] * (max_row_len - len(row)))\n",
    "\n",
    "        return grid\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def calDepth(root: Optional[TreeNode]) -> int:\n",
    "            h = -1\n",
    "            q = [root]\n",
    "            while q:\n",
    "                h += 1\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for node in tmp:\n",
    "                    if node.left:\n",
    "                        q.append(node.left)\n",
    "                    if node.right:\n",
    "                        q.append(node.right)\n",
    "            return h\n",
    "        res = list()\n",
    "        if root is None:\n",
    "            return res\n",
    "        depth = calDepth(root) + 1\n",
    "        maxWidth = 2**depth - 1\n",
    "\n",
    "        level_i = 0\n",
    "        queue = list()\n",
    "        queue.append((root, ((maxWidth - 1) // 2)))\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            level = [\"\"] * maxWidth\n",
    "            for i in range(n):\n",
    "                node, index = queue.pop(0)\n",
    "                level[index] = str(node.val)\n",
    "                if node.left is not None:\n",
    "                    queue.append((node.left, index - 2**(depth - level_i - 2)))\n",
    "                if node.right is not None:\n",
    "                    queue.append((node.right, index + 2**(depth - level_i - 2)))\n",
    "            res.append(level)\n",
    "            level_i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    height = 0\n",
    "\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "\n",
    "        def getHeight(root: TreeNode, h):\n",
    "            if not root:\n",
    "                self.height = max(self.height, h)\n",
    "                return\n",
    "            getHeight(root.left, h + 1)\n",
    "            getHeight(root.right, h + 1)\n",
    "\n",
    "        def func(node: TreeNode, res: List[List], x: int, y: int):\n",
    "            if not node:\n",
    "                return\n",
    "            res[x][y] = str(node.val)\n",
    "            t = 2 ** (self.height - x - 1)\n",
    "            func(node.left, res, x + 1, y - t)\n",
    "            func(node.right, res, x + 1, y + t)\n",
    "\n",
    "        getHeight(root, -1)\n",
    "        m = self.height + 1\n",
    "        n = 2 ** m - 1\n",
    "        res = [[\"\"] * (2 ** m - 1) for _ in range(m)]\n",
    "        func(node=root, res=res, x=0, y=(n - 1) // 2)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def calDepth(node: Optional[TreeNode]) -> int:\n",
    "            d1 = calDepth(node.left)+1 if node.left else 0\n",
    "            d2 = calDepth(node.right)+1 if node.right else 0\n",
    "            return max(d1, d2)\n",
    "        height = calDepth(root)\n",
    "\n",
    "        m = height + 1\n",
    "        n = 2 ** m - 1\n",
    "        ans = [[''] * n for _ in range(m)]\n",
    "\n",
    "        def dfs(node: Optional[TreeNode], r: int, c: int) -> None:\n",
    "            ans[r][c] = str(node.val)\n",
    "            if node.left:\n",
    "                dfs(node.left, r+1, c - 2 ** (height-r-1))\n",
    "            if node.right:\n",
    "                dfs(node.right, r+1, c + 2 ** (height-r-1))\n",
    "        \n",
    "        dfs(root, 0, (n-1)//2)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def depth(root) -> int:\n",
    "            if root is None:\n",
    "                return 0\n",
    "            return max(depth(root.left), depth(root.right)) + 1\n",
    "        res = []\n",
    "        for i in range(depth(root)):\n",
    "            temp = [''] * (2 ** depth(root) - 1)\n",
    "            res.append(temp)\n",
    "        \n",
    "        def constuct(root, left, right, line, res) -> None:\n",
    "            if root is None:\n",
    "                return\n",
    "            res[line][left + (right - left) // 2] = str(root.val)\n",
    "            constuct(root.left, left, left + (right - left) // 2 - 1, line + 1, res)\n",
    "            constuct(root.right,  left + (right - left) // 2 + 1, right, line + 1, res)\n",
    "        constuct(root, 0, 2 ** depth(root) - 1 - 1, 0, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        mid=self.depths(root)#找到根节点\n",
    "        res=[[\"\"]*(2**(mid)-1) for _ in range (mid)]\n",
    "        res[0][(2**(mid)-1)//2]=str(root.val)#根节点入矩阵\n",
    "        queue=[(root,0,(2**(mid)-1)//2)]\n",
    "        depth=0\n",
    "        while depth<mid:\n",
    "            nodes=[]\n",
    "            for node in queue:\n",
    "                n,r,c=node#题目中的n,r,c用于表示矩阵\n",
    "                if n:\n",
    "                    if n.left:\n",
    "                        res[r+1][c-2**(mid-r-2)]=str(n.left.val)\n",
    "                        nodes.append((n.left,r+1,c-2**(mid-r-2)))\n",
    "                    if n.right:\n",
    "                        res[r+1][c+2**(mid-r-2)]=str(n.right.val)\n",
    "                        nodes.append((n.right,r+1,c+2**(mid-r-2)))\n",
    "            queue=nodes\n",
    "            depth+=1\n",
    "        return res\n",
    "        #先计算深度，然后遍历填入节点\n",
    "    def depths(self,root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        ldepth=self.depths(root.left)\n",
    "        rdepth=self.depths(root.right)\n",
    "        return max(ldepth,rdepth)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def getHeight(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        return 1 + max(self.getHeight(root.left), self.getHeight(root.right))\n",
    "\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        height = self.getHeight(root)-1\n",
    "        print(height)\n",
    "        matrix = [[\"\" for i in range(2**(height+1)-1)] for _ in range(height+1)]\n",
    "        nodes = [(root, 2**(height)-1)]\n",
    "        x = 0\n",
    "        while x < height+1:\n",
    "            new_nodes = []\n",
    "            for node, y in nodes:\n",
    "                matrix[x][y] = str(node.val)\n",
    "                if node.left:\n",
    "                    new_nodes.append((node.left,y-2**(height-x-1)))\n",
    "                if node.right:\n",
    "                    new_nodes.append((node.right,y+2**(height-x-1)))\n",
    "            nodes = new_nodes    \n",
    "            x += 1\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "\n",
    "        def cal_height(root):\n",
    "            l = cal_height(root.left) + 1 if root.left else 0     \n",
    "            r = cal_height(root.right) + 1 if root.right else 0 \n",
    "            return max(l, r)\n",
    "        height = cal_height(root) if root else 0 \n",
    "        m, n =  height + 1, 2 **(height + 1) -1 \n",
    "        ans = [[''] * n for _ in range(m)]\n",
    "        def dfs(node: Optional[TreeNode], r: int, c: int) -> None:\n",
    "            ans[r][c] = str(node.val)\n",
    "            if node.left:\n",
    "                 dfs(node.left, r + 1, c - 2 ** (height - r - 1))\n",
    "            if node.right:\n",
    "                dfs(node.right, r + 1, c + 2 ** (height - r - 1))\n",
    "        dfs(root, 0, (n - 1) // 2)\n",
    "        return ans\n",
    "\n",
    "\n",
    "                \n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def dfs(node: TreeNode) -> int:\n",
    "            return max(dfs(node.left), dfs(node.right)) + 1 if node else 0\n",
    "        \n",
    "        def dfsTree(node: TreeNode, r: int, c: int):\n",
    "            ans[r][c] = str(node.val)\n",
    "            diff = 2 ** (height - 2 - r)\n",
    "            if node.left:\n",
    "                dfsTree(node.left, r + 1, c - diff)\n",
    "            if node.right:\n",
    "                dfsTree(node.right, r + 1, c + diff)\n",
    "        \n",
    "        height = dfs(root)\n",
    "        ans = [[\"\"] * (2 ** height - 1) for _ in range(height)]\n",
    "        dfsTree(root, 0, (len(ans[0]) - 1) // 2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def calculate_depth(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            left_depth = calculate_depth(root.left)\n",
    "            right_depth = calculate_depth(root.right)\n",
    "            return max(left_depth, right_depth)+1\n",
    "        heigh = calculate_depth(root)\n",
    "\n",
    "        res, que = [[\"\"]*(2**(heigh)-1) for i in range(heigh)], [(root,0,(2**(heigh)-1-1)//2)]\n",
    "        while que:\n",
    "            tem,r,c = que.pop(0)\n",
    "            res[r][c] = f'{tem.val}'\n",
    "            if tem.left:que.append((tem.left,r+1,c-(2**(heigh-r-2))))\n",
    "            if tem.right:que.append((tem.right,r+1,c+(2**(heigh-r-2))))\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def calDepth(node):\n",
    "            return max(calDepth(node.left)+1 if node.left else 0,calDepth(node.right)+1 if node.right else 0)\n",
    "        \n",
    "        height=calDepth(root)\n",
    "        m=height+1\n",
    "        n=2**m-1\n",
    "\n",
    "        ans=[['']*n for _ in range(m)]\n",
    "        def dfs(node,r,c):\n",
    "            ans[r][c]=str(node.val)\n",
    "            if node.left:\n",
    "                dfs(node.left,r+1,c-2**(height-r-1))\n",
    "            if node.right:\n",
    "                dfs(node.right,r+1,c+2**(height-r-1))\n",
    "        dfs(root,0,(n-1)//2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(dfs(root.left),dfs(root.right))+1\n",
    "        \n",
    "        m=dfs(root)\n",
    "        n=2**m-1\n",
    "        res=[[\"\"]*n for _ in range(m)]\n",
    "        r=0\n",
    "        c=(n-1)//2\n",
    "        \n",
    "        def dfs1(root,d,c):\n",
    "            if not root:\n",
    "                return \n",
    "            res[d][c]=str(root.val)\n",
    "            if root.left:\n",
    "                dfs1(root.left,d+1,c-2**(m-2-d))\n",
    "            if root.right:\n",
    "                dfs1(root.right,d+1,c+2**(m-2-d))\n",
    "        \n",
    "        dfs1(root,r,c)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\r\n",
    "        # ret=[]\r\n",
    "        def get_depth(root:TreeNode):\r\n",
    "            if not root:\r\n",
    "                return 0\r\n",
    "            return 1+max(get_depth(root.left),get_depth(root.right))\r\n",
    "\r\n",
    "        rows=get_depth(root)\r\n",
    "        cols=2**rows-1\r\n",
    "        ret=[['']*cols for _ in range(rows)]\r\n",
    "        def build(root:TreeNode,depth,left,right):\r\n",
    "            if not root:\r\n",
    "                return\r\n",
    "            center=(left+right)//2\r\n",
    "            ret[depth][center]=str(root.val)\r\n",
    "            build(root.left,depth+1,left,center-1)\r\n",
    "            build(root.right,depth+1,center+1,right)\r\n",
    "        \r\n",
    "        build(root,0,0,cols-1)\r\n",
    "        return ret\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def dfs(node):\n",
    "            return 0 if not node else max(dfs(node.left), dfs(node.right)) + 1\n",
    "        h = dfs(root)\n",
    "        ans = [[''] * (2 ** h - 1) for _ in range(h)]\n",
    "        q = deque([(root, 2 ** (h-1) - 1)])\n",
    "        for i in range(h):\n",
    "            for _ in range(len(q)):\n",
    "                node, j = q.popleft()\n",
    "                ans[i][j] = str(node.val)\n",
    "                if node.left:\n",
    "                    q.append((node.left, j - 2**(h-i-2)))\n",
    "                if node.right:\n",
    "                    q.append((node.right, j + 2**(h-i-2)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def height(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return -1\n",
    "        \n",
    "        if root.left is None and root.right is None:\n",
    "            return 0\n",
    "\n",
    "        left_height = self.height(root.left)\n",
    "        right_height = self.height(root.right)\n",
    "\n",
    "        return max(left_height, right_height)+1\n",
    "\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        if root is None:\n",
    "            return [[\"\"]]\n",
    "        \n",
    "        if root.left is None and root.right is None:\n",
    "            return [[str(root.val)]]\n",
    "\n",
    "        self.height = self.height(root)\n",
    "        self.res = [[\"\" for i in range(pow(2, self.height+1)-1)] for j in range(self.height+1)]\n",
    "\n",
    "        self.layout(root, 0, pow(2, self.height)-1)\n",
    "        return self.res\n",
    "    \n",
    "    def layout(self, root: TreeNode, row, col):\n",
    "        if root is None:\n",
    "            return\n",
    "        \n",
    "        self.res[row][col] = str(root.val)\n",
    "        \n",
    "        if root.left is None and root.right is None:\n",
    "            return\n",
    "        \n",
    "        self.layout(root.left, row+1, col-pow(2, self.height-row-1))\n",
    "        self.layout(root.right, row+1, col + pow(2, self.height-row-1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def get_depth(node, depth):\n",
    "            if not node: return depth-1\n",
    "            return max(get_depth(node.left, depth+1), get_depth(node.right, depth+1))\n",
    "\n",
    "        depth = get_depth(root, 0)\n",
    "        m, n = depth + 1, 2**(depth+1)-1\n",
    "        grid = [[\"\"]* n for i in range(m)]\n",
    "\n",
    "        queue = [[(root, (n-1)/2)]]\n",
    "        i = 0\n",
    "        while queue:\n",
    "            nodes = queue.pop(0)\n",
    "            next = []\n",
    "            for node, idx in nodes:\n",
    "                idx = int(idx)\n",
    "                grid[i][idx] = str(node.val)\n",
    "                if node.left: next.append((node.left, idx-2**(depth-i-1)))\n",
    "                if node.right: next.append((node.right, idx+2**(depth-i-1)))\n",
    "            if next: queue.append(next)\n",
    "            i += 1\n",
    "        \n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        # calculate height\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(dfs(root.left), dfs(root.right)) + 1\n",
    "\n",
    "        # \n",
    "        def dfsTree(root, r, c):\n",
    "            res[r][c] = str(root.val)\n",
    "            diff = 2**(m - r -2)\n",
    "            if root.left:\n",
    "                dfsTree(root.left, r+1, c-diff)\n",
    "            if root.right:\n",
    "                dfsTree(root.right, r+1, c+diff)\n",
    "        \n",
    "        m = dfs(root)\n",
    "        n = 2 ** m - 1\n",
    "        res = [[\"\"] * n for _ in range(m)]\n",
    "        dfsTree(root, 0, (n-1)//2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printTree(self, root: TreeNode) -> List[List[str]]:\n",
    "        def height(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(height(root.left), height(root.right)) + 1\n",
    "\n",
    "\n",
    "        h = height(root)\n",
    "        width = 2 ** h - 1\n",
    "        res = [[\"\" for _ in range(width)] for _ in range(h)]\n",
    "\n",
    "\n",
    "        def dfs(root, h, l, r):\n",
    "            if not root:\n",
    "                return\n",
    "            m = l + (r - l) // 2\n",
    "            res[h][m] = str(root.val)\n",
    "            dfs(root.left, h + 1, l, m - 1)\n",
    "            dfs(root.right, h + 1, m + 1, r)\n",
    "\n",
    "\n",
    "        dfs(root, 0, 0, width - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def depth(node:TreeNode):\n",
    "            return max( depth(node.left) , depth(node.right)) + 1 if node else 0\n",
    "        \n",
    "        max_depth = depth(root)\n",
    "        res = [ [\"\"] * ( 2**max_depth - 1) for _ in range(max_depth)]\n",
    "        width = 2**max_depth - 1\n",
    "        def dfs(root , depth , start , end):\n",
    "            res[depth ][( end + start )//2] = str(root.val)\n",
    "            if root.left:\n",
    "                dfs(root.left , depth + 1 , start , (end+start) //2)\n",
    "            if root.right:\n",
    "                dfs(root.right , depth +1  ,(start +end ) //2 ,end )\n",
    "        dfs(root ,0 ,0 ,width)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def getDepth(node):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            return max(getDepth(node.left), getDepth(node.right)) + 1\n",
    "        r = getDepth(root)\n",
    "        c = 2 ** r - 1\n",
    "\n",
    "        ans = [[\"\" for _ in range(c)] for _ in range(r)]\n",
    "        def dfs(node, y, x):\n",
    "            ans[y][x] = str(node.val)\n",
    "            dy, dx = 1, 2 ** (r - y - 2)\n",
    "            if node.left:\n",
    "                dfs(node.left, y+dy, x - dx)\n",
    "            if node.right:\n",
    "                dfs(node.right, y+dy, x + dx)\n",
    "\n",
    "        dfs(root, 0, (c - 1) // 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        # 深度优先搜索得到二叉树高度\n",
    "        def depth(node):\n",
    "            if not node: return 0\n",
    "            return max(depth(node.left), depth(node.right))+1\n",
    "        height = depth(root)\n",
    "        # print(height)\n",
    "        n = pow(2, height)-1\n",
    "\n",
    "        res = [[\"\"]*n for _ in range(height)]\n",
    "\n",
    "        def matrix(pos, node):\n",
    "            if not node: return\n",
    "            if not pos:\n",
    "                r, c = 0, int((n-1)/2)\n",
    "            else:\n",
    "                r, c = pos[0], pos[1]\n",
    "            res[r][c] = str(node.val)\n",
    "            matrix([r+1, c-pow(2, height-r-2)], node.left)\n",
    "            matrix([r+1, c+pow(2, height-r-2)], node.right)\n",
    "\n",
    "        matrix(None, root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def depth(node):\n",
    "            if not node: return 0\n",
    "            return max(depth(node.left),depth(node.right))+1\n",
    "\n",
    "        row = depth(root)\n",
    "        col = pow(2,row)-1\n",
    "        res = [['']*col for _ in range(row)]\n",
    "        que = deque([(root,0,(col-1)//2,1)])\n",
    "        while que:\n",
    "            node,x,y,level = que.popleft()\n",
    "            res[x][y]=str(node.val)\n",
    "            if node.left:\n",
    "                que.append((node.left,x+1,y-pow(2,row-level-1),level+1))\n",
    "            if node.right:\n",
    "                que.append((node.right,x+1,y+pow(2,row-level-1),level+1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        def depth(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            return 1 + max(depth(node.left), depth(node.right))\n",
    "        \n",
    "        def dfs(i, j, node, width):\n",
    "            if not node:\n",
    "                return\n",
    "            res[i][j] = str(node.val)\n",
    "            shift = (width//2+1)//2\n",
    "            dfs(i+1, j-shift, node.left, width//2)\n",
    "            dfs(i+1, j+shift, node.right, width//2)\n",
    "        \n",
    "        dtot = depth(root)\n",
    "        wtot = 2**dtot-1\n",
    "        res = [['']*wtot for _ in range(dtot)]\n",
    "        dfs(0, wtot//2, root, wtot)\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def getHeight(node: Optional[TreeNode]):\n",
    "            return 0 if not node else max(getHeight(node.left), getHeight(node.right)) + 1\n",
    "        height = getHeight(root) - 1\n",
    "        ans = [[\"\"] * (pow(2, height+1) - 1) for _ in range(height+1)]\n",
    "        def dfs(node, i, j):\n",
    "            if not node:\n",
    "                return\n",
    "            ans[i][j] = str(node.val)\n",
    "            dfs(node.left, i+1, j-pow(2, height-i-1))\n",
    "            dfs(node.right, i+1, j+pow(2, height-i-1))\n",
    "        dfs(root, 0, len(ans[0])//2)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def cald(node):\n",
    "            ret=0\n",
    "            if node.left:\n",
    "                ret=max(ret,cald(node.left))\n",
    "            if node.right:\n",
    "                ret=max(ret,cald(node.right))\n",
    "            return ret+1\n",
    "        m=cald(root)\n",
    "        n=2**m-1\n",
    "        ans=[[\"\" for _ in range(2**m-1)]for _ in range(m)]\n",
    "        def dfs(node,r,c):\n",
    "            ans[r][c]=str(node.val)\n",
    "            if node.left:\n",
    "                dfs(node.left, r + 1, c - 2 ** (m - r - 2))\n",
    "            if node.right:\n",
    "                dfs(node.right, r + 1, c + 2 ** (m - r - 2))\n",
    "        dfs(root, 0, (n - 1) // 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        def height(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return 1 + max(height(root.left), height(root.right))\n",
    "        \n",
    "        def update(node, left, right, row, res):\n",
    "            if not node:\n",
    "                return \n",
    "            mid = (left + right)//2\n",
    "            res[row][mid] = str(node.val)\n",
    "            if node.left:\n",
    "                update(node.left, left, mid-1, row+1, res)\n",
    "            if node.right:\n",
    "                update(node.right, mid+1, right, row+1, res)\n",
    "                \n",
    "        h = height(root)\n",
    "        w = 2**h - 1\n",
    "        res = [['']*w for i in range(h)]\n",
    "        update(root, 0, w-1, 0, res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import math\n",
    "import collections\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.h = 0\n",
    "        self.c = 0\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        #get node num and h\n",
    "        n = 0\n",
    "        self.h = self.DFS_Depth(root)\n",
    "        #print(\"h\",self.h)\n",
    "        #print(Solution.t_cnt)\n",
    "        #init ret\n",
    "        self.c = int(2**(self.h) - 1)\n",
    "        ret = [[\"\"]*self.c for i in range(self.h)]\n",
    "        #print(ret)\n",
    "        self.BFS(root,ret)\n",
    "\n",
    "\n",
    "\n",
    "        return ret\n",
    "    #DFS遍历tree获取深度\n",
    "    def DFS_Depth(self,tree):\n",
    "        if tree != None:\n",
    "            l = 1+self.DFS_Depth(tree.left)\n",
    "            r = 1+self.DFS_Depth(tree.right)\n",
    "            return max(l,r)\n",
    "        else:\n",
    "            return 0\n",
    "    #BFS遍历tree填充结果矩阵\n",
    "    def BFS(self,tree,ret):\n",
    "        help_q = deque()\n",
    "        help_q.append(tree)\n",
    "        help_dict = {}#key:node,val:(r,c)\n",
    "        help_dict[tree] = (0,int((self.c-1)/2))\n",
    "        while help_q:\n",
    "            level_nodes = deque()\n",
    "            while len(help_q)>0:\n",
    "                node = help_q.popleft()\n",
    "                \n",
    "                r,c = help_dict[node]\n",
    "                print(r,c)\n",
    "                #放入结果矩阵\n",
    "                ret[r][c] = str(node.val)\n",
    "                if node.left:\n",
    "                    level_nodes.append(node.left)\n",
    "                    help_dict[node.left] = (int(r+1),int(c-(2**(self.h-1-r-1))))\n",
    "                if node.right:\n",
    "                    level_nodes.append(node.right)\n",
    "                    help_dict[node.right] = (int(r+1),int(c+(2**(self.h-1-r-1))))\n",
    "            #将level_nodes全部放入help_q\n",
    "            while level_nodes:\n",
    "                help_q.append(level_nodes.popleft())\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def get_depth(node, depth):\n",
    "            if not node: return depth-1\n",
    "            return max(get_depth(node.left, depth+1), get_depth(node.right, depth+1))\n",
    "\n",
    "        depth = get_depth(root, 0)\n",
    "        m, n = depth + 1, 2**(depth+1)-1\n",
    "        grid = [[\"\"]* n for i in range(m)]\n",
    "\n",
    "        queue = [[(root, (n-1)/2)]]\n",
    "        i = 0\n",
    "        while queue:\n",
    "            nodes = queue.pop(0)\n",
    "            next = []\n",
    "            for node, idx in nodes:\n",
    "                idx = int(idx)\n",
    "                grid[i][idx] = str(node.val)\n",
    "                if node.left: next.append((node.left, idx-2**(depth-i-1)))\n",
    "                if node.right: next.append((node.right, idx+2**(depth-i-1)))\n",
    "            if next: queue.append(next)\n",
    "            i += 1\n",
    "        \n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def get_depth(node, depth):\n",
    "            if not node: return depth-1\n",
    "            return max(get_depth(node.left, depth+1), get_depth(node.right, depth+1))\n",
    "\n",
    "        depth = get_depth(root, 0)\n",
    "        m, n = depth + 1, 2**(depth+1)-1\n",
    "        grid = [[\"\"]* n for i in range(m)]\n",
    "\n",
    "        queue = [[(root, (n-1)/2)]]\n",
    "        i = 0\n",
    "        while queue:\n",
    "            nodes = queue.pop(0)\n",
    "            next = []\n",
    "            for node, idx in nodes:\n",
    "                idx = int(idx)\n",
    "                grid[i][idx] = str(node.val)\n",
    "                if node.left: next.append((node.left, idx-2**(depth-i-1)))\n",
    "                if node.right: next.append((node.right, idx+2**(depth-i-1)))\n",
    "            if next: queue.append(next)\n",
    "            i += 1\n",
    "        \n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def calDepth(node: Optional[TreeNode]) -> int:\n",
    "            return max(calDepth(node.left) + 1 if node.left else 0, calDepth(node.right) + 1 if node.right else 0)\n",
    "        height = calDepth(root)\n",
    "        m = height + 1\n",
    "        n = 2 ** m - 1\n",
    "        ans = [[''] * n for _ in range(m)]\n",
    "        def dfs(node: Optional[TreeNode], r: int, c: int) -> None:\n",
    "            ans[r][c] = str(node.val)\n",
    "            if node.left:\n",
    "                dfs(node.left, r + 1, c - 2 ** (height - r - 1))\n",
    "            if node.right:\n",
    "                dfs(node.right, r + 1, c + 2 ** (height - r - 1))\n",
    "        dfs(root, 0, (n - 1) // 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def caldepth(node):\n",
    "            return max(caldepth(node.left)+1 if node.left else 0,caldepth(node.right)+1 if node.right else 0)\n",
    "        height=caldepth(root)\n",
    "        m=height+1\n",
    "        n=2**m-1\n",
    "        ans=[['']*n for _ in range(m)]\n",
    "        def dfs(node,r,c):\n",
    "            ans[r][c]=str(node.val)\n",
    "            if node.left:\n",
    "                dfs(node.left,r+1,c-2**(height-r-1))\n",
    "            if node.right:\n",
    "                dfs(node.right,r+1,c+2**(height-r-1))\n",
    "        dfs(root,0,(n-1)//2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        depth = self.calcDepth(root) - 1\n",
    "        m, n = depth + 1, 2 ** (depth + 1) - 1\n",
    "        ans = [[\"\" for _ in range(n)] for _ in range(m)]\n",
    "        # 放置根节点\n",
    "        r, c = 0, (n - 1) // 2\n",
    "        ans[r][c] = str(root.val)\n",
    "        # 分别递归放置左右子节点\n",
    "        self.printNode(root.left, depth, ans, 0, r, c)\n",
    "        self.printNode(root.right, depth, ans, 1, r, c)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def calcDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        return max(1 + self.calcDepth(root.left), 1 + self.calcDepth(root.right))\n",
    "\n",
    "    def printNode(self, node: Optional[TreeNode], depth: int, ans: List[List[str]], direction: int, root_r: int, root_c: int) -> None:\n",
    "        # direction=0: 左子树；direction=1: 右子树\n",
    "        if not node:\n",
    "            return\n",
    "        node_v = 2 ** (depth - root_r - 1)\n",
    "        node_c = root_c + node_v if direction else root_c - node_v\n",
    "        node_r = root_r + 1\n",
    "        ans[node_r][node_c] = str(node.val)\n",
    "        # 递归放置左右子树\n",
    "        self.printNode(node.left, depth, ans, 0, node_r, node_c)\n",
    "        self.printNode(node.right, depth, ans, 1, node_r, node_c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def calDepth(node: Optional[TreeNode]) -> int:\n",
    "            return max(calDepth(node.left) + 1 if node.left else 0, calDepth(node.right) + 1 if node.right else 0)\n",
    "        height = calDepth(root)\n",
    "\n",
    "        m = height + 1\n",
    "        n = 2 ** m - 1\n",
    "        ans = [[''] * n for _ in range(m)]\n",
    "        def dfs(node: Optional[TreeNode], r: int, c: int) -> None:\n",
    "            ans[r][c] = str(node.val)\n",
    "            if node.left:\n",
    "                dfs(node.left, r + 1, c - 2 ** (height - r - 1))\n",
    "            if node.right:\n",
    "                dfs(node.right, r + 1, c + 2 ** (height - r - 1))\n",
    "        dfs(root, 0, (n - 1) // 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        #计算树高度，构造布局结构\n",
    "        def height(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(height(root.left), height(root.right)) + 1\n",
    "        \n",
    "        #height 从0开始\n",
    "        def put(matrix, root, r, c, hi):\n",
    "            matrix[r][c] = str(root.val)\n",
    "            if root.left:\n",
    "                put(matrix, root.left, r + 1, c-2**(hi-r-1),hi)\n",
    "            if root.right:\n",
    "                put(matrix, root.right, r + 1, c+2**(hi-r-1),hi)\n",
    "\n",
    "        \n",
    "        hi = height(root)\n",
    "        #构造布局结构\n",
    "        m, n = hi, 2**hi - 1\n",
    "        res = [[\"\"] * n for _ in range(m)]\n",
    "        put(res, root, 0, (n - 1)//2, hi - 1)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def calDepth(node: Optional[TreeNode]) -> int:\n",
    "            return max(calDepth(node.left) + 1 if node.left else 0, calDepth(node.right) + 1 if node.right else 0)\n",
    "        height = calDepth(root)\n",
    "\n",
    "        m = height + 1\n",
    "        n = 2 ** m - 1\n",
    "        ans = [[''] * n for _ in range(m)]\n",
    "        def dfs(node: Optional[TreeNode], r: int, c: int) -> None:\n",
    "            ans[r][c] = str(node.val)\n",
    "            if node.left:\n",
    "                dfs(node.left, r + 1, c - 2 ** (height - r - 1))\n",
    "            if node.right:\n",
    "                dfs(node.right, r + 1, c + 2 ** (height - r - 1))\n",
    "        dfs(root, 0, (n - 1) // 2)\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import math\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        m = 0\n",
    "        def dfs(node, depth):  # 先DFS获取该树的深度m\n",
    "            nonlocal m\n",
    "            m = max(m, depth) \n",
    "            if node.right: dfs(node.right, depth + 1)\n",
    "            if node.left: dfs(node.left, depth + 1)\n",
    "        dfs(root, 1)\n",
    "        n = pow(2, m) - 1 # 计算列数\n",
    "        res = [['' for _ in range(n)]for _ in range(m)]  # 构造字符串矩阵\n",
    "        res[0][(n-1)//2] = str(root.val)\n",
    "\n",
    "        def dfs(node, r, c):\n",
    "            nonlocal res\n",
    "            res[r][c] = str(node.val)\n",
    "            if node.left: dfs(node.left, r+1, c-pow(2, m-1-r-1))\n",
    "            if node.right: dfs(node.right, r+1, c+pow(2, m-1-r-1))\n",
    "        dfs(root, 0, (n-1)//2)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        queue, d = deque([root]), 1 \n",
    "        while queue:\n",
    "            for _ in range(len(queue)):  # 遍历当前层节点\n",
    "                node = queue.popleft()\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "\n",
    "        # get tree height\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "\n",
    "            return max(dfs(node.left),dfs(node.right))+1\n",
    "\n",
    "        def dfstree(node,r,c):\n",
    "            ans[r][c] = str(node.val)\n",
    "            diff = 2 ** (height - 2 - r)\n",
    "            # print(height,r,diff)\n",
    "            if node.left:\n",
    "                dfstree(node.left, r + 1, c - diff)\n",
    "            if node.right:\n",
    "                dfstree(node.right, r + 1, c + diff)\n",
    "\n",
    "        height = dfs(root)\n",
    "        # 节点个数是2 ** height - 1)\n",
    "        ans = [[\"\"] * (2 ** height - 1) for _ in range(height)]\n",
    "        # print(ans)\n",
    "        dfstree(root, 0, (len(ans[0]) - 1) // 2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def calldepth(node):\n",
    "            return max(calldepth(node.left) + 1 if node.left else 0, calldepth(node.right) + 1 if node.right else 0)\n",
    "        height = calldepth(root)\n",
    "\n",
    "        m = height + 1\n",
    "        n = 2**m - 1\n",
    "        ans = [[''] * n for _ in range(m)]\n",
    "        def dfs(node, r, c):\n",
    "            ans[r][c] = str(node.val)\n",
    "            if node.left:\n",
    "                dfs(node.left, r + 1, c - 2 ** (height - r - 1))\n",
    "            if node.right:\n",
    "                dfs(node.right, r + 1, c + 2 ** (height - r -1))\n",
    "        dfs(root, 0 , (n - 1) // 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import math\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        m = 0\n",
    "        def dfs(node, depth):  # 先DFS获取该树的深度m\n",
    "            nonlocal m\n",
    "            m = max(m, depth) \n",
    "            if node.right: dfs(node.right, depth + 1)\n",
    "            if node.left: dfs(node.left, depth + 1)\n",
    "        dfs(root, 1)\n",
    "        n = pow(2, m) - 1 # 计算列数\n",
    "        res = [['' for _ in range(n)]for _ in range(m)]  # 构造字符串矩阵\n",
    "        res[0][(n-1)//2] = str(root.val)  \n",
    "\n",
    "        queue = deque([(root, 0, (n-1)//2)])  # 初始化根节点在顶行的位置\n",
    "        while queue:\n",
    "            node, r, c = queue.popleft()\n",
    "            res[r][c] = str(node.val)\n",
    "            if node.left: queue.append((node.left, r+1, c-pow(2, m-1-r-1)))\n",
    "            if node.right: queue.append((node.right, r+1, c+pow(2, m-1-r-1)))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "\n",
    "        node_list = [root]\n",
    "        tier = 1\n",
    "        while node_list:\n",
    "            temp = []\n",
    "            for node in node_list:\n",
    "                # x,y = node_dict[node]\n",
    "                if node.left:\n",
    "                    # node_dict[node.left] = (tier, y-1)\n",
    "                    temp.append(node.left)\n",
    "                if node.right:\n",
    "                    # node_dict[node.right] = (tier, y+1)\n",
    "                    temp.append(node.right)\n",
    "            tier+=1\n",
    "            node_list = temp\n",
    "        col_len = 2**(tier-1)-1\n",
    "\n",
    "        ans = [ ['']*col_len  for _ in range(tier-1) ]\n",
    "        mid = (col_len-1)//2\n",
    "        # node_dict.pop(root)\n",
    "        node_dict = {root:(0,mid)}\n",
    "        ans[0][mid] = str(root.val)\n",
    "        node_list = [root]\n",
    "        while node_list:\n",
    "            temp = []\n",
    "            for node in node_list:\n",
    "                x,y = node_dict[node]\n",
    "                point = tier-x-3\n",
    "                if node.left:\n",
    "                    nx = x+1\n",
    "                    ny = y-2**point\n",
    "                    ans[nx][ny] = str(node.left.val)\n",
    "                    node_dict[node.left] = (nx, ny)\n",
    "                    temp.append(node.left)\n",
    "                if node.right:\n",
    "                    nx = x+1\n",
    "                    ny = y+2**point\n",
    "                    ans[nx][ny] = str(node.right.val)\n",
    "                    node_dict[node.right] = (nx, ny)\n",
    "                    temp.append(node.right)\n",
    "\n",
    "            node_list = temp\n",
    "        # for key,(x,y) in node_dict.items():\n",
    "        #     parent_y = (mid+y+1)//2\n",
    "        #     parent_x = x-1\n",
    "        #     ans[x][parent_y-2**(tier-parent_x)] = str(key.val)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def depth(node:TreeNode):\n",
    "            return max( depth(node.left) , depth(node.right)) + 1 if node else 0\n",
    "        max_depth = depth(root)\n",
    "        width = 2**max_depth - 1\n",
    "        \n",
    "        res = [ [\"\"] * width for _ in range(max_depth)]\n",
    "        \n",
    "\n",
    "        def dfs(root , depth ,pos): #开始结束值，每个节点的值在开始结束索引的中间\n",
    "            res[depth][pos] = str(root.val) \n",
    "            if root.left:  \n",
    "                dfs(root.left , depth + 1 , pos - 2**(max_depth - depth - 2) )\n",
    "            if root.right:\n",
    "                dfs(root.right , depth +1  , pos + 2**(max_depth - depth - 2) )\n",
    "        dfs(root ,0 ,(width - 1) // 2 )\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def gaodu(self,jiedianx):\n",
    "        if jiedianx==None:\n",
    "            return 0\n",
    "        else:\n",
    "            return max(self.gaodu(jiedianx.left), self.gaodu(jiedianx.right))+1\n",
    "    \n",
    "    def digui(self,jiedianx, r, c, res,height):\n",
    "        print(r,c)\n",
    "        res[r][c]= str(jiedianx.val)\n",
    "        if jiedianx.left:\n",
    "            \n",
    "            self.digui(jiedianx.left, r+1, c-2**(height-r-1-1),res, height)\n",
    "            \n",
    "        if jiedianx.right:\n",
    "            self.digui(jiedianx.right, r+1, c+2**(height-r-1-1), res, height)\n",
    "        \n",
    "    def printTree(self, root):\n",
    "        # jisuan height\n",
    "        height=self.gaodu(root)\n",
    "        print(height,2222222)\n",
    "        n=2**height -1\n",
    "        m=height\n",
    "        yihang= ['']*n\n",
    "        res=[]\n",
    "        for i in range(m):\n",
    "            res.append(yihang.copy())\n",
    "        r=0\n",
    "        c=int((n-1)/2)\n",
    "        self.digui(root,r, c, res, height)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "\n",
    "        node_list = [root]\n",
    "        tier = 1\n",
    "        while node_list:\n",
    "            temp = []\n",
    "            for node in node_list:\n",
    "                # x,y = node_dict[node]\n",
    "                if node.left:\n",
    "                    # node_dict[node.left] = (tier, y-1)\n",
    "                    temp.append(node.left)\n",
    "                if node.right:\n",
    "                    # node_dict[node.right] = (tier, y+1)\n",
    "                    temp.append(node.right)\n",
    "            tier+=1\n",
    "            node_list = temp\n",
    "        col_len = 2**(tier-1)-1\n",
    "\n",
    "        ans = [ ['']*col_len  for _ in range(tier-1) ]\n",
    "        mid = (col_len-1)//2\n",
    "        # node_dict.pop(root)\n",
    "        node_dict = {root:(0,mid)}\n",
    "        ans[0][mid] = str(root.val)\n",
    "        node_list = [root]\n",
    "        while node_list:\n",
    "            temp = []\n",
    "            for node in node_list:\n",
    "                x,y = node_dict[node]\n",
    "                point = tier-x-3\n",
    "                if node.left:\n",
    "                    nx = x+1\n",
    "                    ny = y-2**point\n",
    "                    ans[nx][ny] = str(node.left.val)\n",
    "                    node_dict[node.left] = (nx, ny)\n",
    "                    temp.append(node.left)\n",
    "                if node.right:\n",
    "                    nx = x+1\n",
    "                    ny = y+2**point\n",
    "                    ans[nx][ny] = str(node.right.val)\n",
    "                    node_dict[node.right] = (nx, ny)\n",
    "                    temp.append(node.right)\n",
    "\n",
    "            node_list = temp\n",
    "        # for key,(x,y) in node_dict.items():\n",
    "        #     parent_y = (mid+y+1)//2\n",
    "        #     parent_x = x-1\n",
    "        #     ans[x][parent_y-2**(tier-parent_x)] = str(key.val)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "\n",
    "        \n",
    "\n",
    "        def dfs(root):\n",
    "            # 求height\n",
    "            if root is None:\n",
    "                return -1\n",
    "            return max(dfs(root.left), dfs(root.right)) + 1\n",
    "        height = dfs(root)\n",
    "\n",
    "        m, n = height+1, (1 << height + 1) -1\n",
    "        res = [[\"\"]*n for _ in range(m)]\n",
    "        print(m, n)\n",
    "        print(res)\n",
    "\n",
    "        def dfs(root, x, y):\n",
    "            # x - level, y - horizontal posi\n",
    "            nonlocal res, height\n",
    "            if root is None:\n",
    "                return\n",
    "            res[x][y] = str(root.val)\n",
    "            if root.left is not None:\n",
    "                dfs(root.left, x+1, y - (1 << (height - x - 1)))\n",
    "            if root.right is not None:\n",
    "                dfs(root.right, x+1, y + (1 << (height - x - 1)))\n",
    "        dfs(root, 0, (n-1) >> 1)\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import math\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        m = 0\n",
    "        def dfs(node, depth):  # 先DFS获取该树的深度m\n",
    "            nonlocal m\n",
    "            m = max(m, depth) \n",
    "            if node.right: dfs(node.right, depth + 1)\n",
    "            if node.left: dfs(node.left, depth + 1)\n",
    "        dfs(root, 1)\n",
    "        n = pow(2, m) - 1 # 计算列数\n",
    "        res = [['' for _ in range(n)]for _ in range(m)]  # 构造字符串矩阵\n",
    "        res[0][(n-1)//2] = str(root.val)  \n",
    "\n",
    "        queue = deque([(root, 0, (n-1)//2)])  # 初始化根节点在顶行的位置\n",
    "        while queue:\n",
    "            node, r, c = queue.popleft()\n",
    "            res[r][c] = str(node.val)\n",
    "            if node.left: queue.append((node.left, r+1, c-pow(2, m-1-r-1)))\n",
    "            if node.right: queue.append((node.right, r+1, c+pow(2, m-1-r-1)))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def depth(node:TreeNode):\n",
    "            return max( depth(node.left) , depth(node.right)) + 1 if node else 0\n",
    "        max_depth = depth(root)\n",
    "       \n",
    "        width = 2**max_depth - 1\n",
    "        \n",
    "        res = [ [\"\"] * width for _ in range(max_depth)]\n",
    "        \n",
    "\n",
    "        def dfs(root , depth ,pos): #开始结束值，每个节点的值在开始结束索引的中间\n",
    "            res[depth][pos] = str(root.val) \n",
    "            if root.left:  \n",
    "                dfs(root.left , depth + 1 , pos - 2**(max_depth - depth - 2) )\n",
    "            #题目中 位置为 c - 2**(height - depth - 1) ,但由于 max_depth已经等于height + 1,所以使用(max_depth - depth - 2)\n",
    "            if root.right:\n",
    "                dfs(root.right , depth +1  , pos + 2**(max_depth - depth - 2) )\n",
    "        dfs(root ,0 ,(width - 1) // 2 )\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        \n",
    "        def getHeight(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            return 1 + max(getHeight(node.left), getHeight(node.right))\n",
    "        \n",
    "        m = getHeight(root)\n",
    "        n = 2 ** m - 1\n",
    "        res = [[''] * (n) for _ in range(m)]\n",
    "\n",
    "        def dfs(node, r, c):\n",
    "            print(r, c)\n",
    "            res[r][c] = str(node.val)\n",
    "            if node.left:\n",
    "                dfs(node.left, r+1, c-2**(m-r-2))\n",
    "            if node.right:\n",
    "                dfs(node.right, r+1, c+2**(m-r-2))\n",
    "        \n",
    "        dfs(root, 0, (n-1)//2)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "\n",
    "        def calDepth(node: Optional[TreeNode]) -> int:\n",
    "            return max(calDepth(node.left) + 1 if node.left else 0, calDepth(node.right) + 1 if node.right else 0)\n",
    "        height = calDepth(root)\n",
    "\n",
    "        m = height + 1\n",
    "        n = 2 ** m - 1\n",
    "        ans = [[''] * n for _ in range(m)]\n",
    "\n",
    "        def dfs(node: Optional[TreeNode], r: int, c: int) -> None:\n",
    "            ans[r][c] = str(node.val)\n",
    "            if node.left:\n",
    "                dfs(node.left, r + 1, c - 2 ** (height - r - 1))\n",
    "            if node.right:\n",
    "                dfs(node.right, r + 1, c + 2 ** (height - r - 1))\n",
    "        dfs(root, 0, (n - 1) // 2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def calHeight(root: TreeNode) -> int:\n",
    "            \"\"\"计算节点的深度，根节点的深度为1\"\"\"\n",
    "            # 递归结束条件：当前节点为空，返回深度0\n",
    "            if not root:\n",
    "                return -1\n",
    "\n",
    "            l = calHeight(root.left)    # max depth of left subtree\n",
    "            r = calHeight(root.right)   # max depth of right subtree\n",
    "            \n",
    "            return max(l, r) + 1\n",
    "        \n",
    "\n",
    "        def dfs(node: Optional[TreeNode], r: int, c: int) -> None:\n",
    "            \"\"\"输入当前节点和其所在位置，根据公式，递归地放置当前节点和左右节点\n",
    "                node: 当前节点\n",
    "                r: 当前节点所在行\n",
    "                c: 当前节点所在列\n",
    "            \"\"\"\n",
    "\n",
    "            # 当前节点的值放在第r行第c列\n",
    "            ans[r][c] = str(node.val)\n",
    "\n",
    "            # 当前节点所在的行和列把剩余空间划分成2部分：左下、右下\n",
    "            # 递归地把左子树放在左下空间\n",
    "            if node.left:\n",
    "                dfs(node.left, r + 1, c - 2 ** (height - r - 1))\n",
    "            # 递归地把左子树放在右下空间\n",
    "            if node.right:\n",
    "                dfs(node.right, r + 1, c + 2 ** (height - r - 1))\n",
    "        \n",
    "        # 计算根节点的高度\n",
    "        height = calHeight(root)\n",
    "\n",
    "        # 构建行数x列数的答案数组，放节点值构成的字符串\n",
    "        m = height + 1  # 行数\n",
    "        n = 2 ** m - 1  # 列数\n",
    "        ans = [[''] * n for _ in range(m)] # 注意不能用 ans = [[''] * n] * m 会造成交叉引用\n",
    "\n",
    "        # 输入根节点和其所在位置，递归根节点\n",
    "        dfs(root, 0, (n - 1) // 2)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        layerOrder = []\n",
    "        stack = collections.deque()\n",
    "        stack.append([root,0])\n",
    "        maxDepth = 0\n",
    "        while(stack):\n",
    "            parentNode,depth = stack.popleft()\n",
    "            layerOrder.append([parentNode.val,depth])\n",
    "            maxDepth = max(depth,maxDepth)\n",
    "            if parentNode.left:\n",
    "                stack.append([parentNode.left,depth+1])\n",
    "            if parentNode.right:\n",
    "                stack.append([parentNode.right,depth+1])\n",
    "        m = depth+1\n",
    "        n = 2**(depth+1)-1\n",
    "        res = [[\"\"]*n for _ in range(m)]\n",
    "        def dfs(root,r,c):\n",
    "            if(root != None):\n",
    "                res[r][int(c)] = str(root.val)\n",
    "                dfs(root.left, r+1, c-2**(depth-r-1))\n",
    "                dfs(root.right, r+1,c+2**(depth-r-1))\n",
    "            \n",
    "        dfs(root, 0, (n-1)/2)\n",
    "        return res\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def max_depth(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            left_height = self.max_depth(root.left)\n",
    "            right_height = self.max_depth(root.right)\n",
    "            return max(left_height, right_height) + 1\n",
    "\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        height = self.max_depth(root)\n",
    "        m = height\n",
    "        n = 2 ** height - 1\n",
    "        result = [[''] * n for _ in range(m)]\n",
    "\n",
    "        queue = [(root, 0, n // 2)]\n",
    "        while queue:\n",
    "            node, row, col = queue.pop(0)\n",
    "            result[row][col] = str(node.val)\n",
    "            if node.left:\n",
    "                queue.append((node.left, row + 1, col - 2 ** (height - row - 2)))\n",
    "            if node.right:\n",
    "                queue.append((node.right, row + 1, col + 2 ** (height - row - 2)))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def calDepth(node: Optional[TreeNode]) -> int:\n",
    "            return max(calDepth(node.left) + 1 if node.left else 0, calDepth(node.right) + 1 if node.right else 0)\n",
    "        height = calDepth(root)\n",
    "\n",
    "        m = height + 1\n",
    "        n = 2 ** m - 1\n",
    "        ans = [[''] * n for _ in range(m)]\n",
    "        def dfs(node: Optional[TreeNode], r: int, c: int) -> None:\n",
    "            ans[r][c] = str(node.val)\n",
    "            if node.left:\n",
    "                dfs(node.left, r + 1, c - 2 ** (height - r - 1))\n",
    "            if node.right:\n",
    "                dfs(node.right, r + 1, c + 2 ** (height - r - 1))\n",
    "        dfs(root, 0, (n - 1) // 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        # 获取树的高度\n",
    "        self.height = 0\n",
    "        def bfs(node,h):\n",
    "            if not node:\n",
    "                self.height = max(self.height, h)\n",
    "                return \n",
    "            bfs(node.left, h+1)\n",
    "            bfs(node.right, h+1)\n",
    "        bfs(root, 0)\n",
    "        m = self.height\n",
    "        n = (2 ** self.height) - 1\n",
    "        res = [[\"\" for _ in range(n)] for _ in range(m)]\n",
    "        height = self.height\n",
    "        #根节点\n",
    "        res[0][(n-1)//2] = str(root.val)\n",
    "        que = collections.deque([(root,(0, (n-1) // 2))])\n",
    "        while que:\n",
    "            node, coordinate = que.popleft()\n",
    "            r = coordinate[0]\n",
    "            c = coordinate[1]\n",
    "            if node.left:\n",
    "                que.append((node.left,(r + 1, c - 2 ** (height - 1 - r - 1)))) \n",
    "                res[r + 1][c - 2 ** (height - 1 - r - 1)] = str(node.left.val)\n",
    "            if node.right:\n",
    "                que.append((node.right,(r + 1 , c + 2 ** (height -1 - r - 1))))\n",
    "                res[r + 1][c + 2 ** (height -1 - r - 1)] = str(node.right.val)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def calHeight(node: Optional[TreeNode]) -> int:\n",
    "            \"\"\"计算当前节点的高度。叶节点的高度为0\"\"\"\n",
    "            if node.left:\n",
    "                l = calHeight(node.left) + 1\n",
    "            else:\n",
    "                l = 0\n",
    "            \n",
    "            if node.right:\n",
    "                r = calHeight(node.right) + 1\n",
    "            else:\n",
    "                r = 0\n",
    "                \n",
    "            return max(l, r)\n",
    "        \n",
    "\n",
    "        def dfs(node: Optional[TreeNode], r: int, c: int) -> None:\n",
    "            \"\"\"输入当前节点和其所在位置，根据公式，递归地放置当前节点和左右节点\n",
    "                node: 当前节点\n",
    "                r: 当前节点所在行\n",
    "                c: 当前节点所在列\n",
    "            \"\"\"\n",
    "\n",
    "            # 当前节点的值放在第r行第c列\n",
    "            ans[r][c] = str(node.val)\n",
    "\n",
    "            # 当前节点所在的行和列把剩余空间划分成2部分：左下、右下\n",
    "            # 递归地把左子树放在左下空间\n",
    "            if node.left:\n",
    "                dfs(node.left, r + 1, c - 2 ** (height - r - 1))\n",
    "            # 递归地把左子树放在右下空间\n",
    "            if node.right:\n",
    "                dfs(node.right, r + 1, c + 2 ** (height - r - 1))\n",
    "        \n",
    "        # 计算根节点的高度\n",
    "        height = calHeight(root)\n",
    "\n",
    "        # 构建行数x列数的答案数组，放节点值构成的字符串\n",
    "        m = height + 1  # 行数\n",
    "        n = 2 ** m - 1  # 列数\n",
    "        ans = [[''] * n for _ in range(m)] # 注意不能用 ans = [[''] * n] * m 会造成交叉引用\n",
    "\n",
    "        # 输入根节点和其所在位置，递归根节点\n",
    "        dfs(root, 0, (n - 1) // 2)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def printTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        def get_height(node):\n",
    "            return 0 if not node else 1 + max(get_height(node.left), get_height(node.right))\n",
    "\n",
    "        def update_output(node, row, left, right):\n",
    "            if not node:\n",
    "                return\n",
    "            mid = (left + right) // 2\n",
    "            self.output[row][mid] = str(node.val)\n",
    "            update_output(node.left, row + 1 , left, mid - 1)\n",
    "            update_output(node.right, row + 1 , mid + 1, right)\n",
    "\n",
    "        height = get_height(root)\n",
    "        width = 2 ** height - 1\n",
    "        self.output = [[''] * width for _ in range(height)]\n",
    "        update_output(node=root, row=0, left=0, right=width - 1)\n",
    "        return self.output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:\n",
    "        def getHeight(node):\n",
    "            if not node.left and not node.right:\n",
    "                return 0\n",
    "            left_height, right_height = 0, 0\n",
    "            if node.left:\n",
    "                left_height = getHeight(node.left)\n",
    "            if node.right:\n",
    "                right_height = getHeight(node.right)\n",
    "            return max(left_height, right_height) + 1\n",
    "        \n",
    "        def buildTree(node, r, c):\n",
    "            if not node:\n",
    "                return\n",
    "            self.matrix[r][c] = str(node.val)\n",
    "            buildTree(node.left, r + 1, c - 2**(self.height - r - 1))\n",
    "            buildTree(node.right, r + 1, c + 2**(self.height - r - 1))\n",
    "        \n",
    "        self.height = getHeight(root)\n",
    "        m, n = self.height + 1, 2**(self.height + 1) - 1\n",
    "        self.matrix = [[\"\"] * n for _ in range(m)]\n",
    "\n",
    "        buildTree(root, 0, (n - 1) // 2)\n",
    "        return self.matrix"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
